import java.io.IOException;
import java.util.HashMap;
import java.util.Stack;


public class LLParser {
	HashMap<String, HashMap<String, String[]>> parseTable;
	String firstNonTerminal;
	public LLParser(HashMap<String, HashMap<String, String[]>> parseTable, String firstNonTerminal) {
		this.parseTable = parseTable;
		this.firstNonTerminal = firstNonTerminal;
	}
	
	public AST parseMiniRE(Token[] tokens) {
		Stack<Pair> stack = new Stack<Pair>();
		stack.push(new Pair(firstNonTerminal, null));
		AST ret = null;
		String[] rule;
		for(int i = 0; i < tokens.length;) {
			rule = null;
			if(parseTable.get(stack.peek().getString()) != null) {
				rule = parseTable.get(stack.peek().getString()).get(tokens[i].getType());
				if(rule == null)
					rule = parseTable.get(stack.peek().getString()).get(tokens[i].getString());
			}
			
			//We found a rule!
			if(rule != null) {
				Pair p = stack.pop();
				AST a = new AST(p.getString(), AST.Type.NONTERMINAL);
				if(ret == null)
					ret = a;
				else
					p.getAST().addChild(a);
				for(int j = rule.length - 1; j >= 0; j--) {
					if(!rule[j].equals("<epsilon>"))
						stack.push(new Pair(rule[j], a));
				}
			} else if(stack.peek().getString().equals(tokens[i].getType())) {  //Found a terminal match, continue past it				
				System.out.println(tokens[i].getString());
				Pair p = stack.pop();
				p.getAST().addChild(new AST(tokens[i].getString(), AST.Type.TOKEN));
				i++;
			} else if(stack.peek().getString().equals(tokens[i].getString())) {  //Found a match, pop it
				System.out.println(tokens[i].getString());
				Pair p = stack.pop();
				p.getAST().addChild(new AST(tokens[i].getString(), AST.Type.TERMINAL));
				i++;
			} else {
				System.out.println("Fail!");
			}
		}
		return ret;
	}

	public void parse(Token[] tokens) {
		Stack<String> stack = new Stack<String>();
		stack.push(firstNonTerminal);
		String[] rule;
		for(int i = 0; i < tokens.length;) {
			rule = null;
			if(parseTable.get(stack.peek()) != null) {
				rule = parseTable.get(stack.peek()).get(tokens[i].getType());
				if(rule == null)
					rule = parseTable.get(stack.peek()).get(tokens[i].getString());
			}
			
			//We found a rule!
			if(rule != null) {
				stack.pop();
				for(int j = rule.length - 1; j >= 0; j--) {
					if(!rule[j].equals("<epsilon>"))
						stack.push(rule[j]);
				}
			} else if(stack.peek().equals(tokens[i].getType())) {  //Found a terminal match, continue past it
				System.out.println(tokens[i].getString());
				stack.pop();
				i++;
			} else if(stack.peek().equals(tokens[i].getString())) {
				System.out.println(tokens[i].getString());
				stack.pop();
				i++;
			} else {
				System.out.println("Fail!");
			}
		}
		
	}
	
	
	
	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		String filename = "miniRERules";
		LLGenerator generator = new LLGenerator(filename);
		LLParser p = generator.getParser();
		
		Scanner scanner = new Scanner("spec.txt", "input.txt");
		Token[] tokens = scanner.getTokens();
		AST a = p.parseMiniRE(tokens);
		a.evaluate();
		  
		//REVariable.replace("$MATCH ([a-zA-Z ])*ment", "", "input1.txt", "output1.txt");
		
	}
	
	private class Pair {
		private String s;
		private AST a;
		public Pair(String s, AST a) {
			this.setString(s);
			this.setAST(a);
		}
		public AST getAST() {
			return a;
		}
		public void setAST(AST a) {
			this.a = a;
		}
		public String getString() {
			return s;
		}
		public void setString(String s) {
			this.s = s;
		}
		
		
	}

}
